package com.lql.hash;

/**
 * 自实现hashTable
 */
public class HashTabDemo {
    public static void main(String[] args) {
        HashTab hashTab = new HashTab(10);
        hashTab.put(new Emp(1, "Allen"));
        hashTab.put(new Emp(2, "Marry"));
        hashTab.list();
    }
}

/**
 * hash表
 */
class HashTab {
    private final EmpLinkedList[] empLinkedLists;
    private final int size;

    public HashTab(int size) {
        this.size = size;
        empLinkedLists = new EmpLinkedList[size];
        for (int i = 0; i < size; i++) {
            //初始化链表数组
            empLinkedLists[i] = new EmpLinkedList();
        }
    }

    /**
     * 添加元素
     *
     * @param emp 待添加的员工
     */
    public void put(Emp emp) {
        //根据员工对象获取散列值
        int hashIndex = hashIndex(emp.id);
        empLinkedLists[hashIndex].add(emp);
    }

    /**
     * 遍历hash表
     */
    public void list() {
        for (int i = 0; i < size; i++) {
            System.out.println("链表" + i + "的值为：");
            empLinkedLists[i].list();
        }
    }

    /**
     * 根据id查找员工
     *
     * @param id id
     */
    public Emp find(int id) {
        //根据id计算散列后的值
        int hashIndex = hashIndex(id);
        return empLinkedLists[hashIndex].find(id);
    }

    /**
     * 根据id删除员工
     *
     * @param id id
     */
    public void del(int id) {
        //根据id计算散列后的值
        int hashIndex = hashIndex(id);
        empLinkedLists[hashIndex].del(id);
    }

    /**
     * 根据id信息计算hash散列值
     *
     * @param id 员工对象
     * @return 返回散列后的值
     */
    private int hashIndex(int id) {
        return id % size;
    }
}

class EmpLinkedList {
    private Emp head = null;

    /**
     * 添加元素到链表，默认id自增长，采用尾插法
     *
     * @param emp 待添加的元素
     */
    public void add(Emp emp) {
        if (head == null) {
            //链表为空
            head = emp;
            return;
        }
        //临时指针，用于遍历链表,找到尾节点
        Emp tempEmp = head;
        while (tempEmp.next != null) {
            tempEmp = tempEmp.next;
        }
        //尾插法插入节点
        tempEmp.next = emp;
    }

    /**
     * 遍历单链表
     */
    public void list() {
        if (head == null) {
            //链表为空
            System.out.println("链表为空！");
            return;
        }
        //临时指针，用于遍历链表
        Emp tempEmp = head;
        while (tempEmp != null) {
            System.out.println(tempEmp);
            tempEmp = tempEmp.next;
        }
    }

    /**
     * 根据ID查询员工
     *
     * @param id 待查找员工id
     * @return 返回员工对象，否则返回空
     */
    public Emp find(int id) {
        if (head == null) {
            //链表为空
            System.out.println("链表为空，未找到");
            return null;
        }
        // 链表不为空
        //临时指针，用于遍历链表
        Emp tempEmp = head;
        while (tempEmp != null) {
            if (id == tempEmp.id) {
                //查找成功
                return tempEmp;
            }
            tempEmp = tempEmp.next;
        }
        //查找失败
        return null;
    }

    /**
     * 根据id删除指定员工
     *
     * @param id 员工id
     */
    public void del(int id) {
        if (head == null) {
            //链表为空
            System.out.println("链表为空，删除失败");
            return;
        }
        if (head.id == id) {
            //头节点为要删除的节点
            head = head.next;
            return;
        }
        //临时指针，用于遍历链表
        Emp tempEmp = head;
        while (tempEmp.next != null) {
            if (id == tempEmp.next.id) {
                //查找成功，删除节点
                tempEmp.next = tempEmp.next.next;
                break;
            }
            tempEmp = tempEmp.next;
        }
    }
}

class Emp {
    public int id;
    public String name;
    public Emp next;//默认为空，指向下个结点的地址

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name +
                '}';
    }
}
